package com.cuz.daileetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cuzz
 * @version 1.0
 * @description: 请你实现一个「数字乘积类」ProductOfNumbers，要求支持下述两种方法：
 * 1.  add(int num)
 * 将数字  num  添加到当前数字列表的最后面。
 * 2. getProduct(int k)
 * 返回当前数字列表中，最后  k  个数字的乘积。
 * 你可以假设当前列表中始终 至少 包含 k 个数字。
 * 题目数据保证：任何时候，任一连续数字序列的乘积都在 32-bit 整数范围内，不会溢出。
 * 示例：
 * 输入：
 * ["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
 * [[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]
 * 输出：
 * [null,null,null,null,null,null,20,40,0,null,32]
 * 解释：
 * ProductOfNumbers productOfNumbers = new ProductOfNumbers();
 * productOfNumbers.add(3);        // [3]
 * productOfNumbers.add(0);        // [3,0]
 * productOfNumbers.add(2);        // [3,0,2]
 * productOfNumbers.add(5);        // [3,0,2,5]
 * productOfNumbers.add(4);        // [3,0,2,5,4]
 * productOfNumbers.getProduct(2); // 返回 20 。最后 2 个数字的乘积是 5 * 4 = 20
 * productOfNumbers.getProduct(3); // 返回 40 。最后 3 个数字的乘积是 2 * 5 * 4 = 40
 * productOfNumbers.getProduct(4); // 返回  0 。最后 4 个数字的乘积是 0 * 2 * 5 * 4 = 0
 * productOfNumbers.add(8);        // [3,0,2,5,4,8]
 * productOfNumbers.getProduct(2); // 返回 32 。最后 2 个数字的乘积是 4 * 8 = 32
 * 提示：
 * add 和 getProduct  两种操作加起来总共不会超过  40000  次。
 * 0 <= num  <=  100
 * 1 <= k <= 40000
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/product-of-the-last-k-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 21:23 2021/9/19
 **/
public class Day2_2 {


    class ProductOfNumbers {
        /**
         * 前缀积
         * 前n个数之积
         */
        private List<Integer> pList;
        /**
         * 最后一个0的位置
         */
        private int lastZeroIndex;


        public ProductOfNumbers() {
            pList = new ArrayList<>();
            //初始化-1 表示没有为0的数
            lastZeroIndex = -1;
        }
        /**
         * @author cuzz
         * @description
         *
         * 1.为什么要记录最后一个0的位置：
         * 如果最后k个数包含了0 那么不用计算直接返回 0 因为任何数乘0等于0
         * 2.前面一个数为0 直接加入，0不影响前缀积的存储
         * @date 22:07 2021/9/19
         **/
        public void add(int num) {
            //如果num为0，将其加到list中，并记录其索引位置
            if (num == 0) {
                pList.add(num);
                lastZeroIndex = pList.size() - 1;
            } else if (pList.size() == 0 || lastZeroIndex == pList.size() - 1) {
                //如果list中没有数 或者前一个数刚好是0，那么直接加到list中
                pList.add(num);
            } else {
                //否则，记录其累乘结果
                pList.add(num * pList.get(pList.size() - 1));
            }
        }
        /**
         * @author cuzz
         * @description
         * 如果没有0：最后k个数之积等于pList.get(size - 1) / pList.get(size - k - 1)
         * 如果最后包含0 直接返回0
         * 如果最后k个数恰好不包含0，那么直接返回pList.get(size - 1);
         * （恰好不包含0 表示 最后k+1个数恰好是0）
         * （直接返回：可以视作0充值了乘积状态）
         * @date 22:09 2021/9/19
         **/
        public int getProduct(int k) {
            int size = pList.size();
            if (size - k <= lastZeroIndex) {
                return 0;
            }
            if (size - k - 1 == lastZeroIndex) {
                return pList.get(size - 1);
            }
            return pList.get(size - 1) / pList.get(size - k - 1);
        }
    }
}
